COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.SKIP TO COLUMN 1 <<goals for AM>>
C00008 00003	.MACRO BOXTOP ⊂
C00053 ENDMK
C⊗;
.SKIP TO COLUMN 1 <<goals for AM>>
.NORMAL
The second system we call ⊗3AM⊗* (⊗3A⊗*utomated ⊗3M⊗*athematician). 
It is designed as a heterarchical pool of small programs, one for
each mathematical concept in AM's repertoire. Such a program represents
AM's knowledge about a particular operator, object, or relationship. 
Since concepts will be represented procedurally, adding new knowledge
is equivalent to synthesizing additional programs.  AM's only activity
will be to augment its store of knowledge,
which means
writing new little programs to add to itself,
and modifying the existing knowledge programs.
AM will initally be given ⊗2universal⊗* concepts,
those needed in every field of mathematics. These concepts include:
sets, relations, properties, problems, problem-solving
proof techniques, analogy; abilities
to evaluate interestingness, to locate relevant knowledge.
AM will use its strategies to compound these into new concepts, new little programs.
Thus, AM is an application of
program-understanding techniques to the acquisition of knowledge.

Ideally, AM will engage in what can be regarded as
mathematical  research:
(i) proposing axiomatizations,
based on AM's earlier successes and/or on simulated
real-world situations;
(ii) proposing  and proving conjectures, using the
heuristics discussed by Polya;
(iii) using intuition, by which we
mean employing simulated real-world scenarios to gather empirical evidence;
(iv) evaluating concepts and theories for aesthetic interest;
and (v) using such judgments to guide development in the most promising direction.

While this goal sounds quite ambitious, several simplifications are planned, to
make this project feasable:

.BEGIN PREFACE 1 INDENT 7,9,5; SPACING 0

(i) Each knowledge program will be small, and constrained to conform to a fixed
format. This reduces the complexity of the automatic coding task.

(ii) By hand, we must codify and encode programs which give AM the needed ability
to automatically acquire knowledge. 
In addition, it won't be necessary to add much specific knowledge about
mathematical constructs, because
AM will be able to augment itself automatically.
Only a small amount of detailed knowledge must thus be supplied initially.

(iii) 
Since AM can develop on its own, the human user need only guide, not teach it.
The basic paradigm for
interacting with AM is: observe its behavior, occasionally interrupt
it and redirect its energies.  
Even when messages ⊗2must⊗* be passed between system and user, the fact that
the domain is elementary mathematics means that 
the language needed to express
those messages can
be fairly simple.
Since the quantity and variety of these
communications are small, the complexity of the communication task is reduced.

.END
In any program-understanding system, we
must distinguish the task of the system from the objectives of the research.
We are working on PUNS to learn about understanding programs, ⊗2not⊗*
because we hope that PUNS will write some super-human concept-formation
program. We are working on AM to see how to apply the techniques of 
program understanding and writing to a particular task not ususally
thought of as program-understanding;
we don't expect   it to produce new mathematical results. 
Each system should, however, provide new insights into how humans write programs
in these domains, and what is required to automate this behavior.
For example, if we strive to include all the obvious judgmental criteria in
AM originally, then when AM falters we can analyze its difficulty
and learn something new about knowledge-manipulating programs. [?]
.MACRO BOXTOP ⊂
.ONCE NOFILL; PREFACE 0; INDENT 0; SELECT 6; TURN ON  "∞→"; TURN OFF "α"
⊂∞α→⊃
.BREAK
.⊃

.MACRO BOXBOT ⊂
.ONCE NOFILL; PREFACE 0; INDENT 0; SELECT 6; TURN ON  "∞→"; TURN OFF "α"
%∞α→$
.BREAK
.⊃

.COMPACT

.SSEC(A Model of Math Research)

AM is an attempt to automate mathematical research, by applying the
techniques and the mechanisms of program-understanding systems.
Of course, to automate anything, one must have a fairly clear model of how
it is done. Thanks to Polya, Kershner, Hadamard, Skemp, and many others,
such a model can be pieced together. Here, in highly abbreviated form,
is such a model:

.BOXTOP

.BEGIN SINGLE SPACE PREFACE 0 INDENT 2,5,2

1. The order of events in a typical mathematical investigation is:
Observe →→→ Notice Regularity →→→ Formalize →→→ Develop the theory.
The observation is either of reality or of an analogous, already-established
mathematical theory.

2. The key to keeping this from becoming a blind, explosive search is the
proper use of evaluation criteria. That is, one must constantly choose the
most interesting, aesthetically pleasing, useful,... concept to expand next.

3. The non-formal criteria (aesthetics, interestingness, intuitive clarity,
utility, analogy, empirical evidence) are much more important than formal
deductive methods in developing mathematically worthwhile theories, and
in avoiding barren diversions.

4. The above criteria are virtually the same in all domains of mathematics,
and at all levels. Each factor encourages some pursuits and discourages others.

5. For true understanding, AM must relate to each concept in several ways:
declarative (definition), operational (how to use it), demonic (recognizing
when it is relevant), exemplary (especially boundary examples), and
intuitive (image of a real-world interpretation).

6. Progress in ⊗2any⊗* field of math demands much intuition (and some
formal knowledge) of ⊗2many⊗* different mathematical fields. So a broad,
universal core of intuition must be established before any single theory
can meaningfully be developed.
.END

.BOXBOT

.SSEC(Designing a System for this task)

1. Representation of knowledge in the system: AM will represent each
concept as a bundle of facets (DEFINITION, INTUITION, RECOGNITION,
INTERESTINGNESS,...), and each facet will be stored internally as a
little program.  Each concept will have precisely the same set of
facets.  This enables us to assemble, in advance, a body of knowledge
(called ⊗2strategic⊗* knowledge) about each facet. This is the same
as the program-understanding representation scheme
PUP6 used. 


2. Control in the system: As AM runs, at each moment, each concept
will have only a few of its facet programs filled in; most of the
facets of most of the concepts will be unknown. AM's only control
structure is to repeatedly choose some facet of some concept, and
then use the appropriate strategic knowledge to fill in that missing
program.  The strategic knowledge will typically access and run many
other facet programs from many other concepts.  In the course of
this, new concepts may be constructed and deemed worth giving names to.
Whenever this happens, the new concept has almost all its facets
blank, which means AM now has about 20 specific tasks to eventually
attend to (if they're deemed interesting enough). So the system never
runs out of things to do; rather, the number of possible 
tasks keeps growing rapidly. 
One reason for actually programming AM is to see how sophiticated
the judgmental criteria must be to control this growth.

3. Program-writing: Recall that each facet is a little program. So
"filling in a facet" means synthesizing a program which meets the
requirements. For facet F of concept C, this requirement is that the
program be able to answer questions about F which might be put to C. 
The know-how to write this program is contained in the strategic
knowledge associated with F. The strategic knowledge is thus also a
program; its "argument" in this case would be C (and implicity, all
the existing concepts), and its "output" would be a little program
which would be filled in as facet F of concept C.  All the techniques
of program-⊗2understanding⊗* are required to interpret the argument C
meaningfully.  All the techniques of automatic program ⊗2synthesis⊗* are
required to assemble the output program correctly. 

4. AM is interactive: AM informs a human user of the things it finds
which it thinks are interesting.  The user can interrupt AM and
interrogate it, redirect its energies, and so on. Since the user has
several roles, AM should have several languages: traditional math
notation, textbook English, formal (e.g. AUTOMATH or predicate
calculus), pictorial (simulated visual intuitions), etc. 

.SSEC(Initial State of AM's Knowledge)

1. Range of concepts provided: AM will be given strategic information for
each kind of facet that a concept can forseeably have, and will be given
some detailed information about the most universal mathematical concepts.
A few of these specific concepts are:
⊗2Objects⊗* (like 
Ordered-pair,
Variable,
List-structure,
Axiom);
⊗2Actives⊗* (like
Compose, Insert, Substitute, 
Undo,
Negate,
Membership,
Equipollence,
Quantification,
Extreme);
⊗2Higher-order Actives⊗* (like
Select, Analogize, 
Assume,
Prove,
Debug,
Communicate,
Select-representation,
Categoricity); and
⊗2Higher-order Objects⊗* (like
Conjecture,
Contradiction, Analogy, 
Problem,
Mathematical-theory).

2. Facets that each concept might have:
Each facet program can be viewed as answering a certain family of questions
about the concept in which it is embedded. For example, the DEFINITION
facet of COMPOSE should be able to tell if any given entity is a composition.
The tentative set of 25 facets that concepts can have breaks into four main
categories:
.SKIP 1
.BEGIN NOFILL PREFACE 0 INDENT 0
⊗2RECOGNITION GROUPING⊗*  Notice when this concept, call it B, is relevant.
⊗2ALTER-ONESELF GROUPING⊗*  Know about variations of B, how good B is, etc.
⊗2ACT-ON-ANOTHER GROUPING⊗*  Look at part of another concept, perhaps do something to it.
⊗2INFO GROUPING⊗* General information about this concept, B, and how it fits in.
.END

3. Actual initial state: After delineating the concepts which will be given, 
and the facets
that a concept might have, there remain two additional knowledge-gathering tasks:
(i) Fill in some of the facets for each of the concepts initially to be supplied,
and (ii) Fill in the strategic information for each facet. For example, the box
below contains the INTERESTINGNESS facet of the concept COMPOSE. That is, it gives
procedures for determining when any specific composition is to viewed as interesting:

.BOXTOP
.BEGIN FILL SPACING 0 PREFACE 0 INDENT 3,6,3 TABBREAK
A composition is interesting if any of the following are true:
	The result satisfies some interesting property 
which is not true of either argument relation.
	Interesting properties of both argument relations are preserved.
	Undesirable properties of both argument relations are lost.
	Interesting subsets (cases) of domain of 1st argument operator map into 
interesting subsets of range of 2nd argument operator.
	Preimages of interesting subsets (cases) of range of  2nd argument
are themselves interesting subsets of domain of 1st argument.
	The range of the first argument operator is equal to, not just a subset of,
the domain of the second argument operator.
.END
.BOXBOT

Notice that the first five factors are all recursive, depending on interestingness
of the arguments, properties, etc. The final hint is ⊗2not⊗* recursive; ultimately,
every interstingness "search" terminates at such factors.
	
.SSEC(The Goal: AM running)

1. No specific goal: One of the flaws of PUP6 was that it had one particular
target. Since PUP6 did synthesize that target, it was never clear precisely
how important various aspects of its design were, and there were no "experiments"
one could run on it. By contrast, AM has no set goal, no target "final state"
of knowledge. Its actions are knowledge acquisition, guided by evaluation
criteria and discovery heuristics. It will be a success if it does something
interesting, if it develops some mathematically interesting concepts (no doubt
ones that are well-known already, like cardinality). This lack of specificity
is considered an advantage, since the system creators can't (even unconsciously)
predetermine what is "necessary" for AM to start with, to acheive a fixed goal.

2. Some possible developments: To say that AM has no specific goal does not mean
that we can't evaluate its performance, or that we have no idea what it might do.
In fact, here is a list of early numerical concepts we expect AM to devlop:
Count, Inverse, Commutativity,
Transitivity, Associativity, Singleton, Function,
Successor, Zero, One, Two, Plus, Times.

3. A hypothetical dialogue with AM: 
Assume that AM has just developed all the
preceding concepts, in addition to its universal store (item * on page *).
Here is how the ensuing dialgoue might appear to the user sitting at a teletype.

.SKIP 1
.BEGIN SELECT 7 FILL; PREFACE 80 MILLS; INDENT 0,4,0; SPACING 0
.TURN OFF "-" TURN ON "↑↓"
.AT "USER:" ⊂}⊗8USER⊗*:{⊃
.AT "SYS:" ⊂}⊗8SYSTEM⊗*:{⊃

SYS: I am looking at more examples of TIMES↑-↑1. 
TIMES↑-↑1(n) seems always to include, as one ordered pair,
(n, 1). Same for (1, n). So I can state:
.ONCE PREFACE 0
Conjecture: (∀xεN)  (x,1) ε TIMES↑-↑1(x), and (1,x) ε TIMES↑-↑1(x).
Proof is simple: TIMES(x,1)=x=TIMES(1,x).

SYS: The two pairs (n,1) and (1,n) 
are distinct iff the number n is not equal to 1.
Noticing the number 1 as an exception, we can state:
.ONCE PREFACE 0
Corollary: COUNT*TIMES↑-↑1(1) = 1;  (∀x>1) COUNT*TIMES↑-↑1(x) ≥ 2.
COUNT * TIMES↑-↑1 is the how many ways one may express a number as a product
of an ordered pair of numbers.

SYS: Interesting to consider the subset P of N, 
defined as α{xεN | COUNT*TIMES↑-↑1(x)=2α}.

USER: (interrupting)  Why is this interesting?

SYS: At the moment, we have the known fact f(x)≥y; try to pin down extreme cases,
those x for which f(x) is precisely equal to y. f is COUNT*TIMES↑-↑1, in the current
case, and y is 2.  Do you have any special names you would like me to refer to
COUNT * TIMES↑-↑1 by? Any special names for the subset P?

USER: Call that composition FAC.
Call the set P, of extreme numbers under FAC, PRIMES.

SYS: Syntactic transformation: "PRIME" is the predicate which means "is in PRIMES".

USER: TIMES may also be viewed as operating on a BAG; 
in this sense, TIMES↑-↑1 would 
return all possible bags (of any length) whose product is the given number. 
We do not allow bags to have <2 members, and we do not allow bags longer than 2
to have any 1's in them.

SYS: In this case, the corollary above just says: COUNT(TIMES↑-↑1(x)) ≥ 1. 
The extremes now are just 1 and PRIMES.   
I want a new name for this new interpretation of TIMES↑-↑1.

USER: Call it FACTORS.

SYS: Conjecture: FACTORS(x) always seems to contain a bag containing only
ones and primes, and only one such bag. 
.ONCE PREFACE 0
Proof of existence is by contradiction,
using the lemma  ¬PRIME(x) → ∃(u,v)εTIMES↑-↑1(x) s.t. 1<u<x, 1<v<x.
.ONCE PREFACE 0
Proof of Uniqueness is by contradiction, using the lemma 
(∀a,bεN, xεPRIMES). x|TIMES(a,b) iff x|a or x|b.

USER: Call this the unique factorization theorem. This is very important.
Consider now the sum of all the divisors of a number.

.END

4. How AM's knowledge interacts to do this:
The following explanation is quite detailed, and may be skipped with no
loss of continuity. It explains how AM "really" will manage to make such
discoveries.
Let's consider just one step in the above dialogue: the interesting leap
from the user's
declaration to call the function FACTORS, and AM's statement of the unique
factorization theorem.
Recall that the control mechanism is just repeatedly select a concept and a
facet, then work to fill in the program for that facet of that concept.
Below, C.F is the notation used for facet F of concept C.

.BEGIN SELECT 7 FILL SINGLE SPACE PREFACE 1 INDENT 0,3,0 TURN OFF "{}-"

i. Choose Concept=FACTORS, Facet=TIES.
Gather relevant algorithms from the facets labelled:
[FACTORS.Ties].Fillin, [FACTORS.Genl-Info].Fillin, [FACTORS.Any-Part].Fillin,
[OPERATION.Ties].Fillin, [OPERATION.Genl-Info].Fillin, [OPERATION.Any-Part].Fillin,
[ACTIVE.Ties].Fillin, [ACTIVE.Genl-Info].Fillin, [ACTIVE.Any-Part].Fillin,
[ANY-concept.Ties].Fillin, [ANY-concept.Genl-Info].Fillin, [ANY-concept.Any-Part].Fillin.

ii. First hint collected says: "Let D be the
known concept representing 
the kind of entity in the
range of FACTORS. Then ask D.INTEREST  how to look for interesting
properties or regularities.  If sparse, ask (generalization↑* D).INTEREST also.
Apply these methods to the output of a typical example of FACTORS.
Check interesting property found, by seeing if it holds
for the other outputs from FACTORS  and ensuring it isn't simply part of the
definition of FACTORS."

iii. Because the output of a call on FACTORS is a ⊗2set⊗* of bags,
we are directed to ask SET.INTEREST for aid
in perceiving interesting things about a particular output,
say the output
{(BAG 3 5 5) (BAG 75) (BAG 5 15) (BAG 3 25)} from the call FACTORS(75).
SET.INTEREST is not very big, so we ask STRUCTURE.INTEREST as well.

iv. STRUCTURE.INTEREST explains that there are three 
distinct ways a structure can be interesting.
First, check whether the structure satisfies any known interesting property of that
type of structure.
If not, check to see whether every element satisfies 
the same interesting property. If not, check to see if ⊗2some⊗* element of the
structure satisfies some very interesting property.
The criteria for interestingness being talked about here is the one specified
by the concept representing the type of the elements. In our present case,
our set is a set of ⊗2bags,⊗* so that
means consult all the hints and factors present under BAG.INTEREST. But this is
also very sparse, hence we recursively turn to 
STRUCTURE.INTEREST for evaluation criteria.

v. After a reasonable time, AM cannot find any interesting property satisfied by the
given output set,
{(BAG 3 5 5) (BAG 75) (BAG 5 15) (BAG 3 25)}.
AM also fails to find any single interesting property satisfied
by all four bags which form the elements of that output set.

vi. Now AM looks at each element in turn, that is, each
bag. First we consider (BAG 75), say. This satisfies the property SINGLETON.
We check with other examples of FACTORS and, sure enough, each one of them
contains, as an element, a bag having the property SINGLETON. Comparing these
singletons to the inputs to FACTORS, we conjecture that 
(BAG x) will always appear in the output set of FACTORS(x).

vii. We go back to looking at the individual bags in FACTORS(75).
This time we
look at (BAG 3 5 5).  Each element ⊗2does⊗* satisfy an interesting property,
namely PRIME. We check against the other examples of FACTORS, and sure enough
each one of them contains an element which is a bag of primes. There doesn't
seem to be any obvious relationship to the input argument, so we merely
conjecture that FACTORS(x) always contains a bag of primes, without saying
which primes or how to compute them. This is one half of the Unique Factorization
Theorem. Notice that this is "rough around the edges", namely for the cases
of factors of zero and one, but these will be caught later by an expert concept
who specializes in checking conjectures just before we start to prove them.


viii. Each element of (BAG 3 5 5) also satisfies the property ODD. But this is quickly
rejected by looking at the example FACTORS(2) = {(BAG 2)}.

ix. We now look at the next individual bag in FACTORS(75), namely (BAG 5 15).
Nothing interesting is found here or in the next case, (BAG 3 25).

x. Instead of going on to prove some of these conjectures, let's see how AM might
notice the uniqueness aspects of them. AM knows that some elements of FACTORS(x)
satisfy MAPSTRUC(PRIME), but some don't. It wants to find out how to characterize
those which do; namely, those bags of primes from those containing a nonprime.
So AM will temporarily create a new concept, called say PF, defined as
⊗7PF(x) = FACTORS(x) ∩ MAPSTRUC(PRIME, x) = {b | BAG(b) ∧ TIMES(b)=x ∧ 1¬εb ∧
∀zεb. PRIME(z)}⊗*.
Which means: all bags of primes whose TIMES is x; which also means all
factorizations of x into bags containing only primes.

xi. In a manner similar to the above, AM will notice that PF of each number seems to
be a SINGLETON. That is, there is only one bag of primes in the FACTORS(x) collection
for a given x.  How does it do this?
The unique factorization theorem can be
consisely be stated as "PF is a function defined on N".
In such a form, it is not surprising that AM will routinely investigate it.

.END
5. Estimates of AM's parameters:

.BEGIN NOFILL INDENT 0 PREFACE 0 TABS 35,45 TURN ON "\" SELECT 1

     NUMBER\Initially\Ultimately
\\ (recall that there is no set "goal", however)
Number of Families of concepts\  5\  5
Number of concepts per family\ 30\100
Number of Parts per concept\ 25\ 25
Size of each part (lines of LISP)\  5\  7
Number of parts filled in\  8\ 20
Size of avg. concept (LISP lines)\ 40\140
Total number of concepts\150\500
Core used by AM\200K\500K
Time per int. result (cpu min)\ 15\  5
CPU time used (hours)\  0\100
.END

6. Estimated timetable for AM:

i. Codify the necessary core of initial knowledge (facts and the wisdom to employ them).
⊗7Reality: See Given Knowledge, as presented in the Second Sketch, 
completed 12/10/74.⊗*

.BEGIN  TURN ON "{"

ii. Formulate a sufficient set of new ideas, design decisions, and intuitive assumptions
to make the task meaninful and feasable.
⊗7Reality: firmed up by February 1, 1975.⊗*

iii. Use these ideas to represent the core knowledge of mathematics collected in (1),
in a concrete, simulated system.
⊗7Reality: the current version of Given Knowledge casts this into the concept-family format.
Hand-simulations done during March, 1975, with this "paper" system.⊗*

iv. Implement a realization of this system as a  computer program.
⊗7Reality: Now under way: {DATE}.⊗*

v. Debug and run the system. Add the natural language abilities gradually, as needed.
⊗7Reality: Scheduled for May to November of 1975.⊗*

.END

vi. Analyze the results obtained from this system, with an eye toward: overall
feasability of automating creative mathematical discovery; adequacy of the initial
core of knowledge; adequacy of the ideas, design decisions, implementation
details, and theoretical assumptions.  Use the results to improve the system;
when "adequate,"  forge ahead as far as possible into as many domains as possible,
then reanalyze. ⊗7Reality: 
the 5↔6 cycle will terminate in the Winter of 1976.⊗*